/*
 * @Author: szx
 * @Date: 2021-11-25 13:21:48
 * @LastEditTime: 2021-11-25 14:04:02
 * @Description:
 * @FilePath: \leetcode\1-99\72\72.js
 */
/**
 * @param {string} word1
 * @param {string} word2
 * @return {number}
 */

//  dp[i][j] 代表 word1 中前 i 个字符，变换到 word2 中前 j 个字符，最短需要操作的次数
var minDistance = function (word1, word2) {
    const m = word1.length,
        n = word2.length;
    const dp = new Array(m + 1).fill(0).map(() => new Array(n + 1).fill(0));
    for (let i = 0; i <= m; i++) {
        dp[i][0] = i;
    }
    for (let j = 0; j <= n; j++) {
        dp[0][j] = j;
    }
    for (let i = 1; i <= m; i++) {
        const c1 = word1[i - 1];
        for (let j = 1; j <= n; j++) {
            const c2 = word2[j - 1];
            if (c1 === c2) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = Math.min(Math.min(dp[i - 1][j] + 1, dp[i][j - 1] + 1), dp[i - 1][j - 1] + 1);
            }
        }
    }
    return dp[m][n];
};
minDistance('distance', 'springbok');
